import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

//递归后序遍历
class Solution {
    TreeNode ans = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        postorder(root, p, q);
        return ans;
    }

    int postorder(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }

        int leftFlag = postorder(root.left, p, q);
        if (leftFlag == 2) {
            return 2;
        }

        int rightFlag = postorder(root.right, p, q);
        if (rightFlag == 2) {
            return 2;
        }

        int rootFlag = root == p || root == q ? 1 : 0;
        rootFlag += leftFlag + rightFlag;

        if (rootFlag == 2) {
            ans = root;
        }
        return rootFlag;
    }
}
